This randomized, prospective Phase I trial of melanoma-associated peptide immunization is intended to define the safety and toxicity of synthetic Melan-A, gp100, and tyrosinase peptide immunization together with the immunologic adjuvant, MF-59, in patients with measurable metastatic melanoma.